#include <iostream>
#include <string>
#include <stack>
#define MAX_VARIABLE_NUM 26
#define STACK_INIT_SIZE 128
#define STACK_INCREMENT 32
using namespace std;

typedef char TElemType;

typedef struct Node
{
    TElemType data;
    struct Node *lchild;
    struct Node *rchild;
} BTNode, BinaryTree;

typedef struct Stack
{
    Node **base;
    Node **top;
    int stacksize;
} SqStack;

void Exit(string message)
{
    cout << "ERROR:" << message << endl;
    exit(1);
}

//初始化栈
void InitSqStack(SqStack &S)
{
    S.base = (BTNode **)malloc(STACK_INIT_SIZE * sizeof(char));
    if (!S.base)
        Exit("Memory Deficiency");
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}

//弹出并返回栈顶元素
bool PopSqStack(Stack &S, BTNode *&e)
{
    if (S.top == S.base)
        return 0;
    e = *S.top;
    return 1;
}

//删除栈顶元素
bool DetopSqStack(Stack &S)
{
    --S.top;
    return 1;
}

//入栈
void Push(Stack &S, BTNode *e)
{
    if (S.top - S.base >= S.stacksize)
    {
        S.base = (BTNode **)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(BTNode *));
        if (!S.base)
            Exit("Stack Overflow");
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *S.top++ = e;
}

//判断栈是否空，空的话返回1， 否则返回0
bool SqStackEmpty(Stack &S)
{
    if (S.base == S.top)
    {
        return 1;
    }
    return 0;
}

// Initialize Binary Tree
void InitBinaryTree(BTNode *&T)
{
    T = NULL;
}

void DestroyBinaryTree(BTNode *&T)
{
    if (T)
    {
        DestroyBinaryTree(T->lchild);
        DestroyBinaryTree(T->rchild);
        delete T;
    }
    T = NULL;
}

void PreOrderTraverse(BTNode *&T, void (*v)(BTNode *&T, char &e))
{
    if (T)
    {
        if (T->data)
            v(T, T->data);
        PreOrderTraverse(T->lchild, v);
        PreOrderTraverse(T->rchild, v);
    }
}
void InOrderTraverse(BTNode *&T, void (*v)(BTNode *&T, char &e))
{
    if (T)
    {
        PreOrderTraverse(T->lchild, v);
        if (T->data)
            v(T, T->data);
        PreOrderTraverse(T->rchild, v);
    }
}
void PostOrderTraverse(BTNode *&T, void (*v)(BTNode *&T, char &e))
{
    if (T)
    {
        PreOrderTraverse(T->lchild, v);
        PreOrderTraverse(T->rchild, v);
        if (T->data)
            v(T, T->data);
    }
}

bool JudgeSimbol(char &c)
{
    switch (c)
    {
    case '&':
    case '~':
    case '+':
    case '(':
    case ')':
        return true;
    default:
        return false;
    }
}

char Precede(char top, char ch)
{
    /*
    char f;
    if (t1 == 0)
    {
        return '<';
    }
    switch (t2)
    {
    case '+':
        if (t1 == '(')
            f = '<';
        else
            f = '>';
        break;
    case '*':
        if (t1 == '*' || t1 == '~' || t1 == ')')
            f = '>';
        else
            f = '<';
        break;
    case '~':
        f = '>';
        break;
    case '(':
        f = '<';
        break;
    case ')':
        if (t1 == '(')
            f = '=';
        else
            f = '>';
        break;
    case '=':
        f = '>';
    }
    return f;
    */
    if (ch == ')' && top == '(')
        return '=';
    else if (ch == ')')
        return '>';
    if (top == ' ' || top == '(' || ch == '(')
        return '<';
    if (ch == '=')
        return '>';
    if (top == '+')
    {
        if (ch == '+')
            return '>';
        else
            return '<';
    }
    if (top == '*')
    {
        if (ch == '~')
        {
            return '<';
        }
        else
        {
            return '>';
        }
    }
}

bool CreateBinaryExpTree(BTNode *&T, char ch[])
{
    stack<BTNode *> OPND, OPTR;
    // InitSqStack(OPND); // 运算符
    // InitSqStack(OPTR); // 表达式二叉树
    BTNode *p, *q, *s;
    int i = 0, m;
    char theta;
    while (!OPTR.empty() || ch[i] != '=')
    {
        if (ch[i] >= 'A' && ch[i] <= 'Z')
        {
            p = new BTNode;
            p->data = ch[i];
            p->lchild = p->rchild = NULL;
            OPND.push(p);
            i++;
        }
        else
        {
            if (OPTR.empty())
            {
                theta = ' ';
            }
            else
            {
                q = OPTR.top();
                theta = q->data;
            }
            switch (Precede(theta, ch[i]))
            {
            case '<':
                q = new BTNode;
                q->data = ch[i];
                q->lchild = q->rchild = NULL;
                OPTR.push(q);
                i++;
                break;
            case '=':
                OPTR.pop();
                i++;
                break;
            case '>':
                s = OPTR.top();
                OPTR.pop();
                if (OPND.empty())
                    return false;
                p = OPND.top();
                OPND.pop();
                if (p->data == '~')
                {
                    q = new BTNode;
                    q->data = NULL;
                    q->rchild = NULL;
                    q->lchild = NULL;
                    s->lchild = p;
                    s->rchild = q;
                    OPTR.push(s);
                    continue;
                }
                if (OPND.empty())
                    return false;
                q = OPND.top();
                OPND.pop();
                s->lchild = q;
                s->rchild = p;
                OPND.push(s);
            }
        }
    }
    T = OPND.top();
    OPND.pop();
    if (OPND.empty())
        return true;
    else
        return false;
}

bool Operate(bool map[MAX_VARIABLE_NUM], char a, char theta, char b = 0)
{
    bool c;
    switch (theta)
    {
    case '+':
        c = map[a - 'A'] + map[b - 'A'];
        break;
    case '~':
        c = !map[a - 'A'];
        break;
    case '*':
        c = map[a - 'A'] * map[b - 'A'];
    }
    return c;
}

char Evaluate(BTNode *&T, bool map[MAX_VARIABLE_NUM])
{
    if (T)
    {
        if (!T->lchild && !T->rchild)
            return T->data;
        return Operate(map, Evaluate(T->lchild, map), T->data, Evaluate(T->rchild, map));
    }
}

void DisplayExp(BTNode *&T, void (*visit)(BTNode *&T, char &e))
{
    char a, b;
    if (T)
    {
        if (T->lchild && T->lchild->lchild && (Precede(a = T->lchild->data, b = T->data) == '<'))
        {
            //根节点及它的左孩子结点都不是树叶
            //若左孩子结点的运算符优先级低则加括号
            cout << "(";
            DisplayExp(T->lchild, visit);
            cout << ")";
        }
        else
        {
            DisplayExp(T->lchild, visit);
        }
        if (T->data)
            visit(T, T->data);
        if (T->rchild && T->rchild->lchild && (Precede(a = T->rchild->data, b = T->data) == '<'))
        {
            cout << "(";
            DisplayExp(T->rchild, visit);
            cout << ")";
        }
        else
        {
            DisplayExp(T->rchild, visit);
        }
    }
}

void Print(BTNode *&T, TElemType &e)
{
    if (!T->lchild && !T->rchild)
        cout << e << "";
    else
    {
        char c = e;
        cout << c << " ";
    }
}

void test()
{
    /*
    cout << "栈能力测试" << endl;
    SqStack p;
    InitSqStack(p);
    BTNode *q = new BTNode;
    q->data = '2';
    q->lchild = q->rchild = NULL;
    Push(p, q);
    PopSqStack(p, q);
    cout << q->data << endl;
    */
    cout << "运算符优先级测试" << endl;
    char x1 = '+';
    char x2 = '+';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x2 = '*';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x2 = '~';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x1 = '*';
    x2 = '+';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x2 = '*';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x2 = '~';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x1 = '~';
    x2 = '+';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x2 = '*';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    x2 = '~';
    cout << x1 << " " << Precede(x1, x2) << " " << x2 << endl;
    exit(0);
}

int main()
{
    // test();
    BinaryTree *BT;
    char ch[256];
    char yes = 'y';
    bool map[MAX_VARIABLE_NUM];
    bool flag = false;
    bool outputed = false;
    // InitBinaryTree(BT);
    cout << "随便输入个逻辑表达式，以=结尾" << endl;
    cin >> ch;
    if (CreateBinaryExpTree(BT, ch))
    {
        cout << "表达式的前缀表示为：" << endl;
        PreOrderTraverse(BT, Print);
        cout << endl;

        cout << "表达式的中缀表示为：" << endl;
        InOrderTraverse(BT, Print);
        cout << endl;

        cout << "表达式的后缀表示为：" << endl;
        PostOrderTraverse(BT, Print);
        cout << endl;

        cout << "表达式为：" << endl;
        DisplayExp(BT, Print);
        cout << endl;
    }
    else
    {
        cout << "表达式输入有误！" << endl;
    }
    for (int i = 0; i < 2; i++)
    {
        map[0] = i;
        for (int j = 0; j < 2; j++)
        {
            map[1] = j;
            for (int k = 0; k < 2; k++)
            {
                map[2] = k;
                for (int m = 0; m < 2; m++)
                {
                    map[3] = m;
                    if (i == 0 && j == 0 && k == 0 && m == 0)
                    {
                        flag = Evaluate(BT, map);
                    }
                    else
                    {
                        if (flag != Evaluate(BT, map) && !outputed)
                        {
                            cout << "不是重言式" << endl;
                            outputed = true;
                        }
                    }
                }
            }
        }
    }
    if (!outputed)
    {
        cout << "是重言式" << endl;
    }
}